/* vim: ft=c */
#ifndef CYCLE_SORT_INCLUDED
#define CYCLE_SORT_INCLUDED
/******************************************************************************
* (c)2020-2025 Michael T. Richter
*
* This software is distributed under the terms of WTFPLv2.  The full terms and
* text of the license can be found at http://www.wtfpl.net/txt/copying
******************************************************************************/
/** @file
 *  @brief Implementation of the cycle sort for integers and generic types.
 *
 *  Cycle sorts are sorts which guarantee that only one move is made for any
 *  item of data in the sort: from its starting position to its sorted
 *  position.  They are typically grossly inefficient unless the movement of
 *  data is very expensive, in which case they are mandatory.
 *
 *  This is an implementation of cycle sorts for integer values only; other data
 *  types can be added easily, however.
 */
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

/**** CONFIGURATION - user-adjustable parameters go here *********************/
/* Note: -DDEFAULT_CSORT_TYPE=<type> in the command line works too.          */
#ifdef DEFAULT_CSORT_TYPE
typedef DEFAULT_CSORT_TYPE csort_t;
#else
typedef int32_t csort_t;
#endif
/*****************************************************************************/

/*! Sort an array of integers (csort_t) in-place with a cycle sort.
 *
 *  @param[in,out]  array      The array to sort.
 *  @param[in]      array_size The number of **elements** in the array.
 */
void cycle_sort(csort_t array[], size_t array_size);

#ifdef CYCLE_SORT_IMPLEMENTATION
/*******************************************************************************
* CYCLE_SORT IMPLEMENTATION SECTION
* =================================
*
* In a single source file in your project, the symbol CYCLE_SORT_IMPLEMENTATION
* must be defined before including the header:
*
*   ```c
*   #define CYCLE_SORT_IMPLEMENTATION
*   #include "cycle_sort.h"
*   ```
*
* All other source files using this library must *not* define this symbol.
*******************************************************************************/

#ifdef DEBUG
#include <stdio.h>
#define DEBUG_OUT(F, ...) fprintf(stderr, F, __VA_ARGS__)
#else
#define DEBUG_OUT(F, ...)
#endif

/* skip past set of duplicated values */
static inline size_t cs_static_dup_adj(csort_t a[], size_t p, csort_t v)
{
    while (a[p] == v)
    {
        ++p;
    }

    return p;
}

static inline size_t cs_static_get_pos(csort_t a[], size_t s, size_t f, csort_t v)
{
    size_t p = s;

    for (size_t i = s + 1; i < f; i++)
    {
        if (a[i] < v)
        {
            ++p;
        }
    }

    return p;
}

static inline csort_t cs_static_repl(csort_t a[], size_t p, csort_t v)
{
    csort_t t = a[p];
    a[p] = v;
    return t;
}

void cycle_sort(csort_t a[], size_t s)
{
    if (s < 2) return;
    for (size_t i = 0; i < s - 1; i++)
    {
        csort_t v = a[i];
        size_t p = cs_static_get_pos(a, i, s, v);

        if (p == i) // already in the right place
        {
            continue;
        }

        p = cs_static_dup_adj(a, p, v);
        v = cs_static_repl(a, p, v);

        while (p != i)
        {
            p = cs_static_get_pos(a, i, s, v);
            p = cs_static_dup_adj(a, p, v);
            v = cs_static_repl(a, p, v);
        }
    }
}
#endif //CYCLE_SORT_IMPLEMENTATION

#endif //CYCLE_SORT_INCLUDED
